package com.sheng.leetcode.year2025.month09.day05;

import org.junit.Test;

/**
 * @author by ls
 * @date 2025/9/5
 * <p>
 * 2749. 得到整数零需要执行的最少操作数<p>
 * <p>
 * 给你两个整数：num1 和 num2 。<p>
 * 在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2^i + num2 。<p>
 * 请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。<p>
 * 如果无法使 num1 等于 0 ，返回 -1 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：num1 = 3, num2 = -2<p>
 * 输出：3<p>
 * 解释：可以执行下述步骤使 3 等于 0 ：<p>
 * - 选择 i = 2 ，并从 3 减去 2^2 + (-2) ，num1 = 3 - (4 + (-2)) = 1 。<p>
 * - 选择 i = 2 ，并从 1 减去 2^2 + (-2) ，num1 = 1 - (4 + (-2)) = -1 。<p>
 * - 选择 i = 0 ，并从 -1 减去 2^0 + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。<p>
 * 可以证明 3 是需要执行的最少操作数。<p>
 * <p>
 * 示例 2：<p>
 * 输入：num1 = 5, num2 = 7<p>
 * 输出：-1<p>
 * 解释：可以证明，执行操作无法使 5 等于 0 。<p>
 * <p>
 * 提示：<p>
 * 1 <= num1 <= 10^9<p>
 * -10^9 <= num2 <= 10^9<p>
 */
public class LeetCode2749 {

    @Test
    public void test() {
        int num1 = 3, num2 = -2;
//        int num1 = 5, num2 = 7;
        System.out.println(new Solution().makeTheIntegerZero(num1, num2));
    }
}

class Solution {
    public int makeTheIntegerZero(int num1, int num2) {
        for (long k = 1; k <= num1 - num2 * k; k++) {
            // Long.bitCount 获取一个数二进制中，1 的数量
            if (k >= Long.bitCount(num1 - num2 * k)) {
                return (int) k;
            }
        }
        return -1;
    }
}

/**
 * 作者：灵茶山艾府
 * 链接：https://leetcode.cn/problems/minimum-operations-to-make-the-integer-zero/solutions/2319632/mei-ju-da-an-pythonjavacgo-by-endlessche-t4co/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
